/*
 * @(#)src/fork.crypto.md/Cellhash.java   2003-06-08
 *
 * Copyright (C) 2010  Daniel Léonard
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */

package ca.forklabs.crypto.md;

import ca.forklabs.baselib.util.Arrays;

/**
 * This class embodies the algorithm for the message digest Cellhash according to:
 * <blockquote>
 * J. Daemen, R. Govaerts, and J. Vandewalle, J. Daemen, R. Govaerts, J. Vandewalle,
 * <i>A framework for the design of one-way hash functions including cryptanalysis of
 * Damg�rd's one-way function based on a cellular automaton</i>, Advances in Cryptology,
 * Proceedings Asiacrypt'91, LNCS 739, H. Imai, R.L. Rivest, and T. Matsumoto, Eds.,
 * Springer-Verlag, 1993, pp. 82-96.
 * </blockquote>
 * It is more elegant to get an instance with the factory method in class
 * {@link java.security.MessageDigest} :
 * <blockquote>
 * <code>MessageDigest cellhash = MessageDigest.getInstance(Fork.Cellhash, Fork.NAME);</code>
 * </blockquote>
 * <b>NOTE</b>: There does not seem to be test vectors for Cellhash, therefore
 * this class cannot be considered to faithfully implement the algorithm,
 * altough it appears to.
 *
 * @author   <a href="mailto:forklabs at gmail.com?subject=fork.crypto.md.Cellhash">Daniel Léonard</a>
 * @version $Revision: 1.4 $
 * @see      ca.forklabs.crypto.Forklabs
 */
public class Cellhash extends AbstractBlockMessageDigest {

//----------------------------
// Class variables
//----------------------------

   /** The length in bytes of the digest. */
   private static final int DIGEST_LEN = 33;

   /** The length in bytes of a block. */
   private static final int BUFFER_LEN = 4;

   /** Indices for step 1. */
   private static final int[] PLUS_1 = new int[] {
  1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,  16,
 17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,  32,
 33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,  48,
 49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,  64,
 65,  66,  67,  68,  69,  70,  71,  72,  73,  74,  75,  76,  77,  78,  79,  80,
 81,  82,  83,  84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95,  96,
 97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112,
113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128,
129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144,
145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160,
161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176,
177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192,
193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208,
209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224,
225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240,
241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256,
  0
   };

   /** Indices for step 1. */
   private static final int[] PLUS_2 = new int[] {
  2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,  16,  17,
 18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,  32,  33,
 34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,  48,  49,
 50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,  64,  65,
 66,  67,  68,  69,  70,  71,  72,  73,  74,  75,  76,  77,  78,  79,  80,  81,
 82,  83,  84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95,  96,  97,
 98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113,
114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129,
130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145,
146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161,
162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177,
178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193,
194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209,
210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225,
226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241,
242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256,   0,
  1,
   };

   /** Indices for step 3. */
   private static final int[] PLUS_3 = new int[] {
  3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,  16,  17,  18,
 19,  20,  21,  22,  23,  24,  25,  26,  27,  28,  29,  30,  31,  32,  33,  34,
 35,  36,  37,  38,  39,  40,  41,  42,  43,  44,  45,  46,  47,  48,  49,  50,
 51,  52,  53,  54,  55,  56,  57,  58,  59,  60,  61,  62,  63,  64,  65,  66,
 67,  68,  69,  70,  71,  72,  73,  74,  75,  76,  77,  78,  79,  80,  81,  82,
 83,  84,  85,  86,  87,  88,  89,  90,  91,  92,  93,  94,  95,  96,  97,  98,
 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114,
115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130,
131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146,
147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162,
163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178,
179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194,
195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210,
211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226,
227, 228, 229, 230, 231, 232, 233, 234, 235, 236, 237, 238, 239, 240, 241, 242,
243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256,   0,   1,
  2,
   };

   /** Indices for step 3. */
   private static final int[] MINUS_3 = new int[] {
254, 255, 256,   0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,
 13,  14,  15,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  27,  28,
 29,  30,  31,  32,  33,  34,  35,  36,  37,  38,  39,  40,  41,  42,  43,  44,
 45,  46,  47,  48,  49,  50,  51,  52,  53,  54,  55,  56,  57,  58,  59,  60,
 61,  62,  63,  64,  65,  66,  67,  68,  69,  70,  71,  72,  73,  74,  75,  76,
 77,  78,  79,  80,  81,  82,  83,  84,  85,  86,  87,  88,  89,  90,  91,  92,
 93,  94,  95,  96,  97,  98,  99, 100, 101, 102, 103, 104, 105, 106, 107, 108,
109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124,
125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140,
141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156,
157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172,
173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188,
189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204,
205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220,
221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232, 233, 234, 235, 236,
237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252,
253,
   };

   /** Indices for step 5. */
   private static final int[] TIMES_10 = new int[] {
  0,  10,  20,  30,  40,  50,  60,  70,  80,  90, 100, 110, 120, 130, 140, 150,
160, 170, 180, 190, 200, 210, 220, 230, 240, 250,   3,  13,  23,  33,  43,  53,
 63,  73,  83,  93, 103, 113, 123, 133, 143, 153, 163, 173, 183, 193, 203, 213,
223, 233, 243, 253,   6,  16,  26,  36,  46,  56,  66,  76,  86,  96, 106, 116,
126, 136, 146, 156, 166, 176, 186, 196, 206, 216, 226, 236, 246, 256,   9,  19,
 29,  39,  49,  59,  69,  79,  89,  99, 109, 119, 129, 139, 149, 159, 169, 179,
189, 199, 209, 219, 229, 239, 249,   2,  12,  22,  32,  42,  52,  62,  72,  82,
 92, 102, 112, 122, 132, 142, 152, 162, 172, 182, 192, 202, 212, 222, 232, 242,
252,   5,  15,  25,  35,  45,  55,  65,  75,  85,  95, 105, 115, 125, 135, 145,
155, 165, 175, 185, 195, 205, 215, 225, 235, 245, 255,   8,  18,  28,  38,  48,
 58,  68,  78,  88,  98, 108, 118, 128, 138, 148, 158, 168, 178, 188, 198, 208,
218, 228, 238, 248,   1,  11,  21,  31,  41,  51,  61,  71,  81,  91, 101, 111,
121, 131, 141, 151, 161, 171, 181, 191, 201, 211, 221, 231, 241, 251,   4,  14,
 24,  34,  44,  54,  64,  74,  84,  94, 104, 114, 124, 134, 144, 154, 164, 174,
184, 194, 204, 214, 224, 234, 244, 254,   7,  17,  27,  37,  47,  57,  67,  77,
 87,  97, 107, 117, 127, 137, 147, 157, 167, 177, 187, 197, 207, 217, 227, 237,
247
      };

   /** The name of this message digest. */
   @SuppressWarnings("nls")
   public static final String NAME = "Cellhash";


//----------------------------
// Instance variables
//----------------------------

   /** Counter for first words. */
   private int first_count = 0;

   /** Preserves the first 7 words. */
   private int[] firsts = new int[7];

   /** The hashing buffer. */
   private boolean[] H = new boolean[257];

   /** Copy of H. */
   private boolean[] Hcopy = new boolean[257];

   /** The buffer to include. */
   private boolean[] A = new boolean[256];


//----------------------------
// Constructor
//----------------------------

   /**
    * Constructor.
    */
   public Cellhash() {
      super(Cellhash.NAME, Cellhash.BUFFER_LEN, Cellhash.DIGEST_LEN);
      this.coreInit();
      }


//---------------------------
// Accessors and mutators
//---------------------------

   /**
    * Changes the number of first words saved.
    * @param   count   the new count.
    */
   protected void setFirstWordCount(int count) {
      this.first_count = count;
      }

   /**
    * Gets the count of the first words saved.
    * @return   the count of the first words saved.
    */
   protected int getFirstWordCount() {
      return this.first_count;
      }

   /**
    * Gets the first word buffer.
    * @return   the first word buffer.
    */
   protected int[] getFirstWords() {
      return this.firsts;
      }

   /**
    * Gets the hashing buffer.
    * @return   the hashing buffer.
    */
   protected boolean[] getHashingBuffer() {
      return this.H;
      }

   /**
    * Changes the hashing buffer.
    * @param   buffer   the new buffer.
    */
   protected void setHashingBuffer(boolean[] buffer) {
      this.H = buffer;
      }

   /**
    * Gets the copy of the hashing buffer.
    * @return   the copy of the hashing buffer.
    */
   protected boolean[] getHashingCopy() {
      return this.Hcopy;
      }

   /**
    * Changes the hashing buffer copy.
    * @param   buffer   the new buffer.
    */
   protected void setHashingCopy(boolean[] buffer) {
      this.Hcopy = buffer;
      }

   /**
    * Gets the include buffer.
    * @return   the include buffer.
    */
   protected boolean[] getIncludeBuffer() {
      return this.A;
      }


//----------------------------
// Concrete core methods
//----------------------------

   @Override
   protected void coreTransform() {
   // buffer contains 4 bytes
      byte[] buffer = this.getBuffer();
      int value = AbstractBlockMessageDigest.makeInt(buffer, 0, 1, 2, 3);
      AbstractBlockMessageDigest.zeroize(buffer);


   // do we preserve this word ?
      int how_many = this.getFirstWordCount();
      if (7 > how_many) {
      // put at its proper place
         boolean[] a = this.getIncludeBuffer();
         Cellhash.putInt(value, how_many * 32, a);
      // preserve
         int[] words = this.getFirstWords();
         words[how_many] = value;
         how_many++;
         this.setFirstWordCount(how_many);
      // not enough to hash yet
         return;
         }

   // shift A
      boolean[] a = this.getIncludeBuffer();
      System.arraycopy(a, 32, a, 0, 224);

   // put our new word into the array
      Cellhash.putInt(value, 224, a);

   // here we go
      int i1, i2, i3;
      boolean[] h = this.getHashingBuffer();
      boolean[] h_copy = this.getHashingCopy();
      boolean[] swap;

      swap = h_copy; h_copy = h; h = swap;
   // step 1  -  h(i) = h(i) ^ (h(i+1) | !h(i+2))   0 <= i < 257
      for (i1 = 0; i1 < 257; i1++) {
         //i2 = (i1 + 1) % 257;
         //i3 = (i1 + 2) % 257;
         i2 = Cellhash.PLUS_1[i1];
         i3 = Cellhash.PLUS_2[i1];
         h[i1] = h_copy[i1] ^ (h_copy[i2] | (!h_copy[i3]));
         }

   // step 2  -  h(0) = !h(0)
      h[0] = !h[0];

      swap = h_copy; h_copy = h; h = swap;
   // step 3  -  h(i) = h(i-3) ^ h(i) ^ h(i+3)   0 <= i < 257
      for (i1 = 0; i1 < 257; i1++) {
         //i2 = (i1 + 254) % 257;  // it is ((i - 3) % 257), but if negative, the modulo is also negative
         //i3 = (i1 + 3) % 257;
         i2 = Cellhash.MINUS_3[i1];
         i3 = Cellhash.PLUS_3[i1];
         h[i1] = h_copy[i2] ^ h_copy[i1] ^ h_copy[i3];
         }

   // step 4  -  h(i) = h(i) ^ a(i-1)  1 <= i < 257
      for (i1 = 1; i1 < 257; i1++) {
         h[i1] = h[i1] ^ a[i1 - 1];
         }

      swap = h_copy; h_copy = h; h = swap;
   // step 5  -  h(i) = h(10*i)   0 <= i < 257
      for (i1 = 0; i1 < 257; i1++) {
         //i2 = (10 * i1) % 257;
         i2 = Cellhash.TIMES_10[i1];
         h[i1] = h_copy[i2];
         }

      this.setHashingBuffer(h);
      this.setHashingCopy(h_copy);
      }

   @Override
   @SuppressWarnings("hiding")
   protected void coreInit() {
      this.setFirstWordCount(0);

      int[] firsts = this.getFirstWords();
      AbstractBlockMessageDigest.zeroize(firsts);

      boolean[] h = this.getHashingBuffer();
      Cellhash.zeroize(h);

      boolean[] h_copy = this.getHashingCopy();
      Cellhash.zeroize(h_copy);

      boolean[] a = this.getIncludeBuffer();
      Cellhash.zeroize(a);
      }

   @Override
   @SuppressWarnings("hiding")
   protected byte[] coreDoFinal() {
      long count = this.getCount();
      int index = (int) (count % 32L);
      int padlen = 31 - index;
      byte[] last = new byte[padlen + 1 + 28];
      int[] firsts = this.getFirstWords();

      last[padlen++] = (byte) (padlen * 8);
      for (int i = 0; i < 7; i++) {
         padlen = AbstractBlockMessageDigest.breakIntBE(firsts[i], last, padlen);
         }

      this.engineUpdate(last, 0, padlen);

      byte[] digest = new byte[Cellhash.DIGEST_LEN];
      boolean[] h = this.getHashingBuffer();
      digest[0] = (byte) ((h[0]) ? 0x01: 0x00);
      for (int i = 0, j = 1, w = 0; j < Cellhash.DIGEST_LEN - 1; i++) {
         w = Cellhash.getInt(i * 32 + 1, h);
         j = AbstractBlockMessageDigest.breakIntBE(w, digest, j);
         }

      this.coreInit();
      return digest;
      }


//---------------------------
// Implemented method from java.lang.Cloneable
//---------------------------

   /**
    * Makes a deep copy of this message digest in its current state.
    * @return   a clone of this message digest instance.
    */
   @Override
   public Object clone() throws CloneNotSupportedException {
      Cellhash cell = (Cellhash) super.clone();
      cell.firsts = this.firsts.clone();
      cell.Hcopy = this.Hcopy.clone();
      cell.H = this.H.clone();
      cell.A = this.A.clone();
      return cell;
      }


//---------------------------
// Class methods
//---------------------------

   /**
    * Puts the 32 bits of the {@code int} into the array starting at offset
    * {@code off}.
    * @param   val   the {@code int}.
    * @param   off   the offset.
    * @param   bits   the bit array.
    */
   private static void putInt(int val, int off, boolean[] bits) {
      int offset = off;
      int j = 31;
      for (int i = 0; i < 32; i++) {
         bits[offset++] = ((val >>> j--) & 0x01) == 1;
         }
      }

   /**
    * Gets the {@code int} starting at the offset {@code off}.
    * @param   off   the offset.
    * @param   bits   the bit array.
    * @return   the {@code int}.
    */
   private static int getInt(int off, boolean[] bits) {
      int val = 0;

      int offset = off;
      for (int i = 0; i < 32; i++) {
         val = (val << 1) | ((bits[offset++]) ? 0x01 : 0x00);
         }

      return val;
      }

   /**
    * Sets all the array values to false.
    * @param   array   the array.
    */
   protected static void zeroize(boolean[] array) {
      Arrays.memset(array, false);
      }

   }

